/*
 * Copyright (C), 2015-2018
 * FileName: Solution024
 * Author:   zhao
 * Date:     2018/11/22 17:14
 * Description: 24. 两两交换链表中的节点
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈24. 两两交换链表中的节点〉
 *
 * @author zhao
 * @date 2018/11/22 17:14
 * @since 1.0.1
 */
public class Solution024 {

    /**************************************
     * 题目
     给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

     示例:

     给定 1->2->3->4, 你应该返回 2->1->4->3.
     说明:

     你的算法只能使用常数的额外空间。
     你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
     **************************************/

    /**************************************
     *
     * 想法：
     *      1. 声明三个变量存储  cur--当前node，preCur--上一个node，preDoubleCur--上一个node的上一个node
     *         声明循环次数num，偶数次的时候就交换
     *         循环，交换
     *
     *         时间复杂度/空间复杂度： n/1
     *         假设数据为，1,2,3,4,5,6，已经循环到4这个数据
     *         cur: val = 4,next=5
     *         preCur: val = 3,next=4
     *         preDoubleCur: val = 2,next=3
     *
     *         交换方式：
     *                  ListNode tmpCur = cur;
     *                  cur = cur.next;
     *
     *                  preDoubleCur.next = tmpCur;
     *                  tmpCur.next = preCur;
     *                  preCur.next = cur;
     *
     *
     *
     * 我的做法
     *      超过70%的测试案例
     *      时间复杂度/空间复杂度： n/1
     * 代码执行过程：
     *
     * 总结：
     *
     * ***********************************/
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode result = head.next;

        ListNode cur = head;
        ListNode preCur = head;
        ListNode preDoubleCur = head;

        int num = 0;

        while (cur != null) {
            num++;
            if (num % 2 == 0) {
                ListNode tmpCur = cur;
                cur = cur.next;

                preDoubleCur.next = tmpCur;
                tmpCur.next = preCur;
                preCur.next = cur;
                continue;
            }
            preDoubleCur = preCur;
            preCur = cur;
            cur = cur.next;

        }
        return result;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public ListNode better(ListNode head) {
        ListNode mid;
        ListNode ans;
        if (head == null || head.next == null) {
            return head;
        }
        ans = head.next;
        while (true) {
            mid = head.next;
            head.next = head.next.next;
            mid.next = head;
            if (head.next != null && head.next.next != null) {
                mid = head.next;
                head.next = head.next.next;
                head = mid;
            } else {
                head = head.next;
                break;
            }

        }
        return ans;
    }

}
